import java.util.Arrays;

import static java.util.Collections.swap;

public class PriorityQueueHeap {
    public int[] array;
    public int usedSize;
    public PriorityQueueHeap(){
        this.array=new int[5];
    }
    public void createArray(int[] arr){
        for (int i = 0; i <arr.length ; i++) {
            array[i]=arr[i];
            usedSize++;
        }
    }
    public void createHeap(int[] array){
        for (int parent=(usedSize-1-1)/2; parent>=0 ; parent--) {
            downAdjust(array,usedSize);
        }
    }
   /*向下调整——大根堆
   每颗子树的根节点parent
   每棵子树是否调整结束的位置usedSise
   * */
    public void downAdjust(int[] array, int parent) {
        int child=2*parent+1;
        while(child<usedSize){//至少有一个左孩子
            if (child+1<usedSize&&array[child]<array[child+1]){
                child++;//child下标一定是最大孩子的下标
            }
            if (array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }
    private void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    //插入元素
    public void push(int val){
        if (isFull()){
            grow(array);
        }
        array[usedSize]=val;
        upAdjust(usedSize);
        usedSize++;
    }
    public void upAdjust(int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if (array[child]>array[parent]){
                swap(array,child,parent);
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull(){
        return usedSize==array.length;
    }
    public int[] grow(int[] array){
        return array= Arrays.copyOf(array,2*array.length);
    }
    //删除
    public int delete(){
        if (isEmpty()){
            return -1;
        }
        int val=array[0];
        swap(array,0,usedSize-1);
        downAdjust(array,usedSize);
        return val;
    }
    public boolean isEmpty(){
        return usedSize==0;
    }
    //获取堆顶元素
    public int peek(){
        if (isEmpty()){
            return -1;
        }
        return array[0];
    }
    public void printHeap() {
        if (isEmpty()) {
            System.out.println("堆为空");
            return;
        }
        for (int i = 0; i < usedSize; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
